#
# @lc app=leetcode.cn id=85 lang=python
#
# [85] 最大矩形
#

# @lc code=start


class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        m, n = len(matrix), len(matrix[0])
        # dp[i,j] = (m,n)代表矩阵大小
        dp = [[0 for __ in range(n)] for _ in range(m)]
        max_ = 0
        # 初始化第一行
        for j in range(n):
            if matrix[0][j] == "0":
                dp[0][j] = (0, 0)
            else:
                dp[0][j] = (1, 1 + (dp[0][j-1][1] if j-1 >= 0 else 0))
            ij = dp[0][j][0]*dp[0][j][1]
            max_ = ij if ij > max_ else max_
        for i in range(1, m):
            for j in range(n):
                if matrix[i][j] == "0":
                    dp[i][j] = (0, 0)

                elif j == 0:
                    dp[i][j] = (1 + dp[i-1][j][0], 1)
                elif matrix[i-1][j] == '0':
                    dp[i][j] = (1, 1+dp[i][j-1][1])
                elif matrix[i][j-1] == '0':
                    dp[i][j] = (1+dp[i-1][j][0], 1)
                else:
                    j_boundary_index = max(j-dp[i][j-1][1], j-dp[i-1][j][1]+1)
                    i_boundary_index = max(i-dp[i][j-1][0]+1, i-dp[i-1][j][0])
                    size_1 = (dp[i-1][j][0]+1, j-j_boundary_index+1)
                    size_2 = (i-i_boundary_index+1, dp[i][j-1][1]+1)
                    dp[i][j] = max(size_1, size_2, key=lambda x: x[0]*x[1])
                ij = dp[i][j][0]*dp[i][j][1]
                max_ = ij if ij > max_ else max_
        for i in range(m):
            print(dp[i])
        return max_

    def others(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        # 每一行转换成一个整数
        nums = [ int(''.join(row), base=2) for row in matrix ]
        ans, N = 0, len(nums)
        for i in range(N):
            j, num = i, nums[i]
            while j < N:
                if i==1:
                    print(i)
                num = num & nums[j]
                if not num:
                    break
                l, curnum = 0, num
                while curnum:
                    print(bin(curnum))
                    l += 1
                    curnum = curnum & (curnum << 1)
                ans = max(ans, l * (j-i+1))
                j += 1
        return ans


matrix = [
    ["0", "1","1","0","1","1","1","1","1","1","1","1","1","1","1","1","1","1","0"],
    ["1", "0","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],
    ["1", "1","0","1","1","1","1","1","1","1","1","1","0","1","1","1","1","1","1"],
    ["1", "1","1","1","1","1","1","1","1","1","1","1","1","0","1","1","1","1","1"],
    ["1", "1","1","1","1","1","1","1","1","1","1","1","1","1","0","1","1","1","1"],
    ["1", "1","1","0","1","1","1","0","1","1","1","1","1","1","1","1","1","0","1"],
    ["1", "0","1","1","1","1","1","1","1","1","1","1","1","1","0","1","1","1","1"],
    ["1", "1","1","1","1","1","1","1","1","1","1","1","1","1","1","0","1","1","0"],
    ["0", "0","1","1","1","1","1","1","1","1","1","1","1","1","1","0","1","1","1"],
    ["1", "1","0","1","1","1","1","1","1","1","0","1","1","1","1","1","1","1","1"],
    ["1", "1","1","1","1","1","1","1","1","0","1","1","1","1","1","1","1","1","1"],
    ["0", "1","1","0","1","1","1","0","1","1","1","1","1","1","1","1","1","1","1"],
    ["1", "1","1","1","0","1","1","1","1","1","1","1","1","1","0","1","1","1","1"],
    ["1", "1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],
    ["1", "1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],
    ["1", "1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","0","1"],
    ["1", "1","1","1","1","1","1","1","0","1","1","0","1","1","0","1","1","1","1"],
    ["1", "1","1","1","1","1","0","1","1","1","1","1","1","1","1","0","1","1","1"]]
matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
s = Solution()
res = s.others(matrix)
print(res)

# @lc code=end
